#include <iostream>
#include "tree_functions.h"
#include <math.h>
#include <string.h>

using namespace std;

/********************************************************************
  These are helper functions used by the main core index functions
 ********************************************************************/

//Used to keep track of the current Node level while printing index
void Index::resetQueue() {
while(queue1.size() > 0)
	queue1.pop();

queue1.push(root);
}

//Prints all the keys in the index
void Index::printKeys() {
	Node *node = root;

	while(node->id != LEAFID) {
		node = ((IndexNode *)node)->nodePtrs[0];
	}

	while(node != NULL) {
		node->printKeysNode();
		node = ((LeafNode *)node)->nextLeaf;
	}
}

//printIndex helper function which prints one level of the index tree
void Index::printLevel() {
	//global queue used to print all nodes in a level
	for(int x=0; x < queue1.size(); x++) {
		Node *temp = queue1.front();
		queue1.pop();
		temp->printKeysNode();
		queue1.push(temp);
	}
	cout << endl;
}

//printIndex helper function which adds nodes into the queue to be printed
void Index::addNodesToQueue(IndexNode* node) {
	for(int x=0; x<(node->q+1); x++)
		queue1.push(node->nodePtrs[x]);
}

//resets the Stack to just the root after every insertRecord operation
void Index::resetStack() {

while(stack1.size() > 1)
	stack1.pop();
}

/********************************************************************
  These are the core index functions
 ********************************************************************/

//Non-recursive function for searching and returning the record associated with searchKey in index
Record * Index::searchRecord(int searchKey) {
	mutex.lock_shared();		//shared mutex for reads, locks at root

	Node *currentNode = root;
	while(currentNode->id != LEAFID) {
		int x = 0;
		while(searchKey > currentNode->keys[x]) {
			x++;
			if(x == currentNode->q)
				break;
		}
		currentNode = ((IndexNode *)currentNode)->nodePtrs[x];
	}

	//returnRecordInLeaf returns NULL if record is not found
	Record * record = ((LeafNode *)currentNode)->returnRecordInLeaf(searchKey);
	return record;
	mutex.unlock();		//Unlock mutex before exiting function


}

//Recursive function for printing index tree
void Index::printIndex() {
	int length=0;

	//queue needed for breadth first traversal of tree
	Node* front= queue1.front();

	if(front->id == INDEXID) {
		length = queue1.size();
		printLevel();
		for(int x=0; x < length; x++) {
			Node *temp = queue1.front();
			queue1.pop();
			addNodesToQueue((IndexNode *)temp);
		}
		printIndex();
	}
	else {
		printLevel();
		resetQueue();
	}

}

//Recursive function to insert a record into the index:
//returns 0 if key associated with record is already in tree, return 1 if successful insert
int Index::insertRecord(int insertKey, Record *record) {
	mutex.lock();	//exclusive lock index starting at root

	//currentNode gets the root off the stack at the first call to insertRecord
	Node* currentNode = (stack1.top())->node;

	if(record) {	//checks to see space is available for a record insertion

		//This if structure takes care of special case of the index consisting of only 1 leaf node
		if(currentNode->id == LEAFID) {

			if(currentNode->isNodeFull()) {		//Case: when root is full
				if(((LeafNode *)currentNode)->insertRecordInLeaf(insertKey, record)) {

					root = ((LeafNode *)currentNode)->splitLeafNode(((LeafNode *)root)->highKey);
					queue1.front() = root;
					stack1.top()->node = root;					mutex.unlock();
					return 1;
				}
				else {	//record is already in index					mutex.unlock();
					return 0;
				}
			}
			else {	//root is not full and has room for another record
				int temp2 = ((LeafNode *)currentNode)->insertRecordInLeaf(insertKey, record);				mutex.unlock();

				return temp2;
			}

		}
		else {	//The index tree contains at least one Index Node
			int x=0;

			//Looks for the correct key and nextNode in the current Node
			while(insertKey > currentNode->keys[x]) {
				x++;
				if(x == currentNode->q)
					break;
			}

			//nextNode points to the nextNode where the record belongs
			Node* nextNode = (((IndexNode *)currentNode)->nodePtrs[x]);

			if(nextNode->id == LEAFID) {	//Recursive calls to insertRecord stop here because nextNode is a leaf

				if(nextNode->isNodeFull()) {	//if the leafnode is full
					if(((LeafNode *)nextNode)->insertRecordInLeaf(insertKey, record)) {		//insert record before splitting
						IndexNode* temp = ((LeafNode *)nextNode)->splitLeafNode(((IndexNode * )currentNode)->highKey);		//splitting the node

						if(!(currentNode->isNodeFull())) {
							((IndexNode *)currentNode)->insertKeyInIndex(temp, x);
							resetStack();							mutex.unlock();

						}
						else {	//Enter here if the current index node before the leafnode is full and needs splitting
							((IndexNode *)currentNode)->insertKeyInIndex(temp, x);

							if(currentNode == root) {	//covers the case when the current index node is the root node
								root = ((IndexNode *)currentNode)->splitIndexNode(((IndexNode *)root)->highKey);
								queue1.front() = root;
								stack1.top()->node = root;
								resetStack();								mutex.unlock();

							}
							else {	//current index node is not the root
								stack1.pop();
								stackElement *prevStack = stack1.top();
								Node *prevNode = prevStack->node;

								IndexNode* temp2 = ((IndexNode *)currentNode)->splitIndexNode(((IndexNode *)prevNode)->highKey);

								while(!stack1.empty()) {	//this while loop keeps splitting the nodes up the tree until an index node is found that is not full
									stackElement* previousStack = stack1.top();
									IndexNode* previousNode = (IndexNode *)(previousStack->node);
									int index = previousStack->index;

									if(previousNode->isNodeFull()) {
										if(root == previousNode) {	//we've split all the way up to the root node
											previousNode->insertKeyInIndex(temp2, index);
											root = previousNode->splitIndexNode(((IndexNode *)root)->highKey);
											queue1.front() = root;
											stack1.top()->node = root;
											resetStack();											mutex.unlock();

											break;
										}
										else {
											stack1.pop();

											stackElement *prevStack = stack1.top();
											Node *prevNode = prevStack->node;

											previousNode->insertKeyInIndex(temp2, index);
											temp2 = previousNode->splitIndexNode(((IndexNode *)prevNode)->highKey);
										}
									}
									else {	//we've reached an index node that is not full and we insert the new key from the split node below.
										previousNode->insertKeyInIndex(temp2, index);
										resetStack();
										mutex.unlock();
										break;
									}
								}

							}
						}
					}
					else {	//record is already in index						mutex.unlock();
						return 0;
					}
				}
				else {	//leaf node is not full and we can insert it in the leaf

					if(((LeafNode *)nextNode)->insertRecordInLeaf(insertKey, record)) {
						resetStack();						mutex.unlock();
						return 1;
					}
					else {	//record is already in index						mutex.unlock();
						return 0;
					}
				}
			}
			else {	//We need to traverse further down the tree to find the leaf node
				stackElement *currentStack = stack1.top();
				stack1.pop();
				currentStack->index = x;
				stack1.push(currentStack);
				stackElement *nextStack = new stackElement;
				nextStack->node = nextNode;
				nextStack->index = 0;
				stack1.push(nextStack);

				mutex.unlock();		//need to unlock mutex or the next recursive call to insertRecord will reach a deadlock
				insertRecord(insertKey, record);
			}
		}

	}
	else {	//Not enough space on disk for an insertion
			cout << "There is not enough space left on disk!!!!!" << endl;
			mutex.unlock();
			return 0;
	}
}




